import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 986. 区间列表的交集
 * https://leetcode-cn.com/problems/interval-list-intersections/
 */
public class Solutions_986 {
    public static void main(String[] args) {
        int[][] A = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
        int[][] B = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
        // output: {{1, 2}, {5, 5}, {8, 10}, {15, 23}, {24, 24}, {25, 25}}

        int[][] result = intervalIntersection(A, B);
        System.out.println(Arrays.deepToString(result));
    }

    // 双指针 + 模拟
    public static int[][] intervalIntersection(int[][] A, int[][] B) {
        if (A.length < 1 || B.length < 1) {
            return new int[0][0];
        }
        int i = 0, j = 0;
        List<int[]> res = new ArrayList<>();

        while (i < A.length && j < B.length) {
            // 较大的开区间
            int open = Math.max(A[i][0], B[j][0]);
            // 较小的闭区间
            int close = Math.min(A[i][1], B[j][1]);

            if (open <= close) {
                // 交集部分：[open, close]
                res.add(new int[]{open, close});
            }
            // 舍弃闭区间较小的一方
            if (A[i][1] < B[j][1]) {
                i ++;
            } else {
                j ++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
